import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BinaryTree {
    //以内部类的方式创建结点
    static class BinaryTreeNode {
        int val;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;

        public BinaryTreeNode(int val) {
            this.val = val;
        }
    }

    int nodeSize = 0;

    int leafCount = 0;

    //根节点
    public BinaryTreeNode root;

    //手动创建一个二叉树
    public void createTree() {
        BinaryTreeNode node1 = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node6 = new BinaryTreeNode(6);

        root = node1;
        node1.leftChild =  node2;
        node2.leftChild = node3;
        node1.rightChild = node4;
        node4.leftChild = node5;
        node4.rightChild = node6;

    }

    //前序遍历
    public void preOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }

        //先访问当前结点
        System.out.print(node.val + " ");
        //访问左子树
        preOrder(node.leftChild);
        //访问右子树
        preOrder(node.rightChild);
    }

    //非递归的前序遍历
    public void preOrderNor(BinaryTreeNode root) {
        //定义一个栈来辅助实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.leftChild;
            }

             //有些结点没有遍历到
             BinaryTreeNode top = stack.pop();
             cur = top.rightChild;
        }
    }

    //中序遍历
    public void inOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }
        
        //先访问左子树
        inOrder(node.leftChild);

        //访问当前节点
        System.out.print(node.val + " ");

        //访问右子树
        inOrder(node.rightChild);
    }

    //非递归的中序遍历
    public void inOrderNor(BinaryTreeNode root) {
        //定义一个栈来辅助实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.leftChild;
            }

            //要打印栈顶元素的值
            BinaryTreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.rightChild;
        }
    }

    public void postOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }

        //先递归访问左子树
        postOrder(node.leftChild);
        //递归访问右子树
        postOrder(node.rightChild);
        //访问当前节点
        System.out.print(node.val + " ");
    }

    //非递归的后序遍历
    public void postOrderNor(BinaryTreeNode node) {
        //利用栈来实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode cur = node;
        //利用pre记录前一个遍历的结点
        BinaryTreeNode pre = null;

        while (cur != null || !stack.isEmpty()) {
            //后序遍历，左右根
            while(cur != null) {
                stack.push(cur);
                cur = cur.leftChild;
            }

            //找到了最左端
            //如果右端为空或者已经遍历过了，那么弹栈并打印
            BinaryTreeNode top = stack.peek();
            //判断栈顶元素的右孩子是否为空或者已经遍历过
            if(top.rightChild == null || pre == top.rightChild) {
                //打印
                System.out.print(top.val + " ");
                //更新pre
                pre = top;
                //弹栈
                stack.pop();
            }else {
                cur = top.rightChild;
            }

        }


    }

    public static void main1(String[] args) {
         BinaryTree binaryTree = new BinaryTree();
         //前序遍历
         binaryTree.createTree();
         System.out.println("前序遍历序列");
         binaryTree.preOrder(binaryTree.root);
         //中序遍历
         System.out.println();
         System.out.println("中序遍历序列");
         binaryTree.inOrder(binaryTree.root);
         System.out.println();
         //后序遍历
         System.out.println("后序遍历序列");
         binaryTree.postOrder(binaryTree.root);
    }

    //二叉树的基本操作
    //获取二叉树中的结点个数
    public int size1(BinaryTreeNode node) {
        if(node == null) {
            return 0;
        }

        return size1(node.leftChild) + size1(node.rightChild) + 1;
    }

    public void size2(BinaryTreeNode root) {
        if(root == null) {
            return;
        }

        this.nodeSize ++;
        size2(root.leftChild);
        size2(root.rightChild);
    }

    //获取叶子结点的个数
    public int getLeafNodeCount1(BinaryTreeNode root) {
        if(root == null) {
            return 0;
        }

        if(root.leftChild == null && root.rightChild == null) {
            return 1;
        }
        return getLeafNodeCount1(root.leftChild) + getLeafNodeCount1(root.rightChild);
    }

    public void getLeafNodeCount2(BinaryTreeNode root) {
        if(root == null) {
            return;
        }

        if(root.rightChild == null && root.leftChild == null) {
            leafCount++;
        }

        //按照先序遍历的访问顺序访问
        getLeafNodeCount2(root.leftChild);
        getLeafNodeCount2(root.rightChild);
    }

    //获取第k层结点的个数
    public int getKLevelCount(BinaryTreeNode root,int k) {
        //整棵树的第k层 = 左子树的第k - 1 层 + 右子树的k - 1层
        if(root == null) {
            return 0;
        }

        if(k == 1) {
            return 1;
        }

        return getKLevelCount(root.leftChild,k - 1) + getKLevelCount(root.rightChild,k - 1);
    }

    //获取二叉树的高度
    public static int getHeight(BinaryTreeNode node) {
        if(node == null) {
            return 0;
        }

        return Math.max(getHeight(node.leftChild),getHeight(node.rightChild)) + 1;
    }

    //检测值为value的值是否存在
    public BinaryTree.BinaryTreeNode find(int value,BinaryTreeNode node) {
        if(node == null) {
            return null;
        }

        if(node.val == value) {
            return node;
        }

        return null;
    }

    //层序遍历
    public void levelOrder(BinaryTreeNode root) {
           //处理特殊情况，如果是空树直接return
        if(root == null) {
            return;
        }

        //建立一个辅助队列
        LinkedList<BinaryTreeNode> queue = new LinkedList<>();
        //将根节点入队
        queue.offer(root);

        //当队列不为空的时候
        while(!queue.isEmpty()) {
            //拿出队头元素
            BinaryTreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            //若左子树不为空，将左子树放入队列
            if(cur.leftChild != null) {
                queue.offer(cur.leftChild);
            }

            if(cur.rightChild != null) {
                queue.offer(cur.rightChild);
            }
        }
    }

    //判断一棵树是不是完全二叉树
    public boolean isComplete() {
        return false;
    }

    public static void main2(String[] args) {
         BinaryTree binaryTree = new BinaryTree();
         binaryTree.createTree();
         int size = binaryTree.size1(binaryTree.root);
         System.out.println(size);
         System.out.println(binaryTree.getKLevelCount(binaryTree.root,3));
         System.out.println(binaryTree.getHeight(binaryTree.root));
    }

    public static void main3(String[] args) {
//        BinaryTree binaryTree1 = new BinaryTree();
//        binaryTree1.root = new BinaryTreeNode(1);
//        binaryTree1.root.leftChild = new BinaryTreeNode(2);
//        binaryTree1.root.rightChild = new BinaryTreeNode(3);
//
//        BinaryTree binaryTree2 = new BinaryTree();
//        binaryTree2.root = new BinaryTreeNode(1);
//        binaryTree2.root.leftChild = new BinaryTreeNode(2);
//        binaryTree2.root.rightChild = new BinaryTreeNode(3);

//        boolean sameTree = BinaryTreeUtil.isSameTree(binaryTree1.root, binaryTree2.root);
//        System.out.println(sameTree);

//        BinaryTree binaryTree3 = new BinaryTree();
//        binaryTree3.root = new BinaryTreeNode(1);
//        binaryTree3.root.leftChild = new BinaryTreeNode(2);
//
//        BinaryTree binaryTree4 = new BinaryTree();
//        binaryTree4.root = new BinaryTreeNode(1);
//        binaryTree4.root.rightChild = new BinaryTreeNode(2);

//        boolean tree = BinaryTreeUtil.isSameTree(binaryTree3.root, binaryTree4.root);
//        System.out.println(tree);

        BinaryTree binaryTree5 = new BinaryTree();
        binaryTree5.root = new BinaryTreeNode(1);
        binaryTree5.root.leftChild = new BinaryTreeNode(2);
        binaryTree5.root.rightChild = new BinaryTreeNode(1);

        BinaryTree binaryTree6 = new BinaryTree();
        binaryTree6.root = new BinaryTreeNode(1);
        binaryTree6.root.leftChild = new BinaryTreeNode(1);
        binaryTree6.root.rightChild = new BinaryTreeNode(2);

        boolean b = BinaryTreeUtil.isSameTree(binaryTree5.root, binaryTree6.root);
        System.out.println(b);
    }

    public static void main4(String[] args) {
        BinaryTree rootBinaryTree = new BinaryTree();
        rootBinaryTree.root = new BinaryTreeNode(3);
        rootBinaryTree.root.leftChild = new BinaryTreeNode(4);
        rootBinaryTree.root.rightChild = new BinaryTreeNode(5);
        rootBinaryTree.root.leftChild.leftChild = new BinaryTreeNode(1);
        rootBinaryTree.root.leftChild.rightChild = new BinaryTreeNode(2);
        rootBinaryTree.root.leftChild.rightChild = new BinaryTreeNode(0);

        BinaryTree subRootBinaryTree = new BinaryTree();
        subRootBinaryTree.root = new BinaryTreeNode(4);
        subRootBinaryTree.root.leftChild = new BinaryTreeNode(1);
        subRootBinaryTree.root.rightChild = new BinaryTreeNode(2);

//        boolean isSubtree = BinaryTreeUtil.isSubtree(rootBinaryTree.root, subRootBinaryTree.root);
//        System.out.println(isSubtree);
    }

    public static void main5(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.root = new BinaryTreeNode(3);
        binaryTree.root.leftChild = new BinaryTreeNode(9);
        binaryTree.root.rightChild = new BinaryTreeNode(20);
        binaryTree.root.rightChild.leftChild = new BinaryTreeNode(15);
        binaryTree.root.rightChild.rightChild = new BinaryTreeNode(7);
//        binaryTree.preOrder(binaryTree.root);
//        System.out.println();
//        binaryTree.preOrderNor(binaryTree.root);

//        binaryTree.inOrder(binaryTree.root);
//        System.out.println();
//        binaryTree.inOrderNor(binaryTree.root);

//        binaryTree.postOrder(binaryTree.root);
//        System.out.println();
//        binaryTree.postOrderNor(binaryTree.root);


    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.createTree();

        //进行后序遍历
        binaryTree.postOrder(binaryTree.root);
        System.out.println();
        //非递归
       binaryTree.postOrderNor(binaryTree.root);
    }
}

